package com.zjsru.oneDay;

/**
 * 补全最短词
 *
 *
 * 举例：
 * 输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
 * 输出："steps"
 * 解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。
 * "step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。
 * "steps" 包含 "t"、"p" 和两个 "s"。
 * "stripe" 缺一个 "s"。
 * "stepple" 缺一个 "s"。
 * 因此，"steps" 是唯一一个包含所有字母的单词。
 */
public class shortword {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int cases[] = new int[26];
        //对 licensePlate 中出现的字母进行计数
        for (int i = 0; i < licensePlate.length(); i++) {
            if (Character.isLetter(licensePlate.charAt(i))) {//charAt(i)获取当前数组下标的值；isLetter方法判断指定字符是否为字母
                cases[Character.toLowerCase(licensePlate.charAt(i)) - 'a']++;//toLowerCase方法转换小写
            }
        }
        //用于记录最终结果的 word 的下标索引
        int resultId = -1;
        for (int i = 0; i < words.length; i++) {
            int onewordcases[] = new int[26];
            //对 words 中的每个单词中出现的字母进行计数
            for (int j = 0; j < words[i].length(); j++) {
                //length()判断字符串对象的长度；length判断字符串数组的长度
                if (Character.isLetter(words[i].charAt(j))) {
                    onewordcases[Character.toLowerCase(words[i].charAt(j)) - 'a']++;
                }
            }
            //遍历两个cases数组，直到找到符合题目的 word
            //要求：licensePlate 中出现的单词均要在 word 中，且出现的次数只能多不能少
            boolean ok = true;
            for (int k = 0; k < 26; k++) {
                if (onewordcases[k] < cases[k]) {
                    ok = false;
                    break;
                }
            }
        //如果找到符合题目的 word 就与之前的候选结果比较优劣
        //索引较小且单词长度最短者优先
            if (ok && (resultId < 0 || words[resultId].length() > words[i].length())) {
                resultId = i;
            }
        }
        return words[resultId];
    }

    public static void main(String[] args){
        shortword shortword = new shortword();
        System.out.println(shortword.shortestCompletingWord( "1s3 Pst",new String[]{"step", "steps", "stripe", "stepple"}));
    }
}